package alg

// 平均时间复杂度, 最好 O(1), 最差 O(n), 平均均摊 O(n)
func Average(arr []int, x int) int  {
	pos := -1
	for k, vo := range arr {
		if x == vo {
			pos = k
		}
	}
	return pos
}

// 均摊时间复杂度, 最好 O(1), 最差 O(n), 平均均衡 O(1)
var Key = 0
var Arr = make([]string, 2)
func Capitation(val string) {
	length := len(Arr)
	if Key >= length {
		new_length := length * 2
		new_arr := make([]string, new_length)
		for i := 0; i < length; i++ {
			new_arr[i] = Arr[i]
		}
		Arr = new_arr
	}
	Arr[Key] = val
	Key++
}